package com.leetcode.partition7;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/2 14:42
 */
public class LC685冗余连接2 {

    public static int[] findRedundantDirectedConnection(int[][] edges) {
        return unionFind(edges);
    }

    public static void main(String[] args) {
//        int[][] edges = {{1, 2}, {2, 3}, {3, 1}};           //有环无冲突
//        int[][] edges = {{1, 2}, {2, 3}, {3, 1}, {4, 2}};   //有换有冲突
//        int[][] edges = {{1, 2}, {1, 3}, {2, 3}};           //无环有冲突
        int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 5}};
        System.out.println(Arrays.toString(findRedundantDirectedConnection(edges)));
    }

    private static int[] unionFind(int[][] edges) {
        int[] inDegree = new int[edges.length + 1];         //顶点的入度
        //统计各个顶点的入度，如有有入度为2的节点，考虑删除一条边，如果剩下的有向边不能形成环，则删除正确
        for (int[] edge : edges) {
            inDegree[edge[1]]++;
        }
        //尝试删除构成入度为2的边，看看是否形成环。因为题目要求有多个符合条件的答案时，返回出现在最后的边，因此进行反向遍历
        for (int i = edges.length - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                //如果不构成环，这条边就是答案
                if (!hasCircleOnDeleteEdge(edges, i)) {
                    return edges[i];
                }
            }
        }
        //尝试删除构成入度为1的边，看看是否形成环
        for (int i = edges.length - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 1) {
                if (!hasCircleOnDeleteEdge(edges, i)) {
                    return edges[i];
                }
            }
        }
        return new int[0];
    }

    private static boolean hasCircleOnDeleteEdge(int[][] edges, int removeEdgeIndex) {
        //尝试移出edges[removeEdgeIndex]这条边后查看是否会形成环
        int[] ancestor = new int[edges.length + 1];
        //并查集初始化
        for (int i = 1; i < ancestor.length; i++) {
            ancestor[i] = i;
        }
        for (int i = 0; i < edges.length; i++) {
            if (i == removeEdgeIndex) continue;         //不进行union就是相当于删除该边
            if (!union(ancestor, edges[i][1], edges[i][0])) {   //union失败，说明存在环
                return true;
            }
        }
        return false;
    }

    private static int find(int[] ancestor, int x) {
        if (ancestor[x] == x) return x;
        return find(ancestor, ancestor[x]);
    }

    private static boolean union(int[] ancestor, int x, int y) {
        int ancestorX = find(ancestor, x), ancestorY = find(ancestor, y);
        //如果根结点都相等，继续合并则会形成环
        if (ancestorX != ancestorY) {
            ancestor[ancestorY] = ancestorX;
            return true;
        }
        //union的话会形成环，因此union失败
        return false;
    }
}
